/**
 * 
 */
package cz.cvut.fit.crhonjar.mi.paa.thames.solver;

import java.util.Arrays;
import java.util.HashSet;

import cz.cvut.fit.crhonjar.mi.paa.thames.Configuration;
import cz.cvut.fit.crhonjar.mi.paa.thames.Item;
import cz.cvut.fit.crhonjar.mi.paa.thames.State;
import cz.cvut.fit.crhonjar.mi.paa.thames.exception.ThamesException;

/**
 * @author Jarec
 * 
 */
public class DynamicProgrammingSolver extends Solver {

	protected static boolean isTrivial(final int i, final int j) {
		if ((i == 0) || (j == 0)) {
			return true;
		}
		return false;
	}

	private State[] cache;

	private State getFromCache(final int i, final int j) {
		return this.cache[(i * (this.capacity + 1)) + j];
	}

	private void setToCache(final int i, final int j, final State s) {
		this.cache[(i * (this.capacity + 1)) + j] = s;
	}

	@Override
	public Configuration solve() throws ThamesException,
			CloneNotSupportedException {

		this.cache = new State[(this.items.size() + 1) * (this.capacity + 1)];

		Arrays.fill(this.cache, null);
		final HashSet<Item> empty = new HashSet<Item>();
		final State zero = new State(empty, 0, 0);
		for (int i = 0; i <= this.items.size(); i++) {

			for (int j = 0; j <= this.capacity; j++) {

				if (DynamicProgrammingSolver.isTrivial(i, j)) {

					this.setToCache(i, j, zero);

				} else {

					final Item item = this.items.get(i - 1);
					final State c0state = this.getFromCache(i - 1, j);

					final int c1index = j - item.getWeight();

					if (c1index < 0) {
						this.setToCache(i, j, c0state);
					} else {
						final State c1state = this.getFromCache(i - 1, c1index);
						if ((c1state.getPrice() + item.getPrice()) > c0state
								.getPrice()) {
							final State s = c1state.clone();
							s.addItem(item);
							this.setToCache(i, j, s);
						} else {
							this.setToCache(i, j, c0state);
						}
					}
				}
			}
		}

		return new Configuration(this.items, this.getFromCache(
				this.items.size(), this.capacity));
	}

}
